package code.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * @ClassName BucketSort
 * @Description 桶排序
 * https://blog.csdn.net/afei__/article/details/82965834
 * @Author za-zhouyunxing
 * @Date 2019/10/31 13:53
 * @Version 1.0
 */
public class BucketSort {
    /**
     * 这里我想举这样一个例子，假设输入元素是均匀分布的浮点数。为什么要选择浮点数呢？因为我觉得这是计数排序中很难处理的一种情况，
     * 计数排序比较适用于整数的情况，如果我们依旧想在线性时间内完成元素的排序，那么桶排序将是一个很好的选择
     * @param args
     */
    public static void main(String[] args) {
        //输入元素均在 [0, 10) 这个区间内
        float[] arr = new float[]{0.12f, 2.2f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f};
        bucketSort(arr);
        printArray(arr);
    }

    private static void bucketSort(float[] arr) {
        //由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
        List<LinkedList<Float>> buckets = new ArrayList<>();
        //元素范围为0-10，所以创建10个桶
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<>());
        }
        // 将输入数据全部放入桶中并完成排序
        for (float data : arr) {
            //获取数据存放桶的序号
            int index = getBucketIndex(data);
            insertSort(buckets.get(index), data);
        }
        //将桶中的元素全部取出来，放入到arr
        int index = 0;
        for (LinkedList<Float> bucket : buckets) {
            for (Float data : bucket) {
                arr[index++] = data;
            }
        }

    }

    private static void insertSort(LinkedList<Float> list, float data) {
        boolean insertFlag = true;
        ListIterator<Float> iterator = list.listIterator();
        while (iterator.hasNext()){
            if (data <= iterator.next()){
                // 把迭代器的位置偏移回上一个位置
                iterator.previous();
                // 把数据插入到迭代器的当前位置
                iterator.add(data);
                insertFlag = false;
            }
            break;
        }
        if (insertFlag){
            // 否则把数据插入到链表末端
            list.add(data);
        }
    }

    /**
     * 计算得到输入元素应该放到哪个桶内
     * @param data
     * @return
     */
    private static int getBucketIndex(float data) {
        // 这里例子写的比较简单，仅使用浮点数的整数部分作为其桶的索引值
        // 实际开发中需要根据场景具体设计
        return (int)data;
    }

    private static void printArray(float[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + ",");
        }
        System.out.println();
    }
}
